package main

//#link: https://leetcode-cn.com/problems/last-stone-weight-ii/
func main() {

}

//每块石头不是减就是加 ，假设石头总和为 sum，减的那部分石头重量为 neg ,则加的石头重量为 sum-neg,最终剩余的石头重量为 (sum-neg)-neg=sum-2*neg
//dp[i][j]表示 前i块手头凑出重量j来 ，得到状态转移方程
// dp[i+1][j]=dp[i][j],j<stones[i]
// dp[i+1][j]=dp[i][j]||dp[i][j-stones[i]],j>=stones[i]
// 要使最终的重量尽可能小，则neg要尽可能的大 当neg=sum/2的时候得到的结果为0
func lastStoneWeightII(stones []int) int {
	length, sum := len(stones), 0
	for _, stone := range stones {
		sum += stone
	}
	m := sum / 2
	dp := make([][]bool, length+1)
	for i := range dp {
		dp[i] = make([]bool, m+1)
	}
	dp[0][0] = true
	for i, stone := range stones {
		for j := 0; j <= m; j++ {
			if j >= stone {
				dp[i+1][j] = dp[i][j] || dp[i][j-stone]
			} else {
				dp[i+1][j] = dp[i][j]
			}
		}
	}
	for j := m; ; j-- {
		if dp[length][j] {
			return sum - 2*j
		}
	}
}
